import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网面试必刷Top101之递归/回溯
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        ArrayList<Integer> list = new ArrayList<>();
        fullPermutation(arr, list);
    }

    /**
     * 没有重复数字的全排列
     * 方法二：回溯插入法(按照字典序进行排序)
     * 时间复杂度：O(N * N!)
     * N是因为取最大值，如果字典序为{1，2，3}时
     * 那么第一个数据的加入前遍历的时间复杂度为O(1)
     * 最后一个数据的加入前遍历的时间复杂度就是O(N)
     * 平均下来为O(N / 2)(最后计算时间复杂度时需要省去系数)
     * N!是因为有N!种情况
     * 空间复杂度：O(N)(全排列一种情况的大小或递归的深度)
     * @param arr
     * @param list
     */
    private static void fullPermutation(int[] arr, ArrayList<Integer> list) {
        if(list.size() == arr.length) {
            System.out.println(list);
            return;
        }
        for(int i = 0; i < arr.length; i++) {
            if(list.contains(arr[i])) {
               continue;
            }
            list.add(arr[i]);
            fullPermutation(arr,list);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 没有重复数字的全排列
     * 方法一：交换法(没有按照字典序进行排序)
     * 时间复杂度：O(N!)
     * 空间复杂度：O(N)(没有保存只打印，因此空间复杂度是递归的深度)
     * @param arr
     * @param index
     */
    private static void fullPermutation(int[] arr, int index) {
        if(index == arr.length - 1) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for(int i = index; i < arr.length; i++) {
            swap(arr, index, i);
            fullPermutation(arr,index + 1);
            swap(arr, index, i);
        }
    }

    private static void swap(int[] arr, int index, int i) {
        int tmp = arr[index];
        arr[index] = arr[i];
        arr[i] = tmp;
    }

    /**
     * 方法一的另一种表现形式，最后会将所有的全排列都保存在list中
     * @param arr 源数组
     * @param index 确认到第几个位置
     * @param list 最后存储所有全排列的线性表
     */
    private static void fullPermutation(int[] arr, int index, List<List<Integer>> list) {
        if(index == arr.length - 1) {
            List<Integer> tmp = new ArrayList<>();
            for(int x : arr) {
                tmp.add(x);
            }
            list.add(tmp);
            return;
        }
        for(int i = index; i < arr.length; i++) {
            swap(arr, index, i);
            fullPermutation(arr,index + 1, list);
            swap(arr, index, i);
        }
    }

    /**
     * 存在重复数据的全排列
     * 方法一：采用哈希表记录每个数据的个数
     * 时间复杂度：O(N * N!)
     * 空间复杂度：O(N)
     * @param num
     * @return
     */
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if(num.length == 0) {
            return ans;
        }
        Arrays.sort(num);
        //1.用哈希表存储数组中的数据，vlaue为个数
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < num.length; i++) {
            if(map.containsKey(num[i])) {
                map.put(num[i], map.get(num[i]) + 1);
            }else {
                map.put(num[i], 1);
            }
        }
        //创建临时链表，通过增删来得到各种情况，并且方便每次从最后一个位置删除
        LinkedList<Integer> list = new LinkedList<>();
        //2.遍历整个数组，仍采用插入法和回溯
        //不过这次的判断条件是哈希表里是否存在
        func(num, list, map, ans);
        return ans;
    }

    private void func(int[] num, LinkedList<Integer> list,
                      HashMap<Integer,Integer> map, ArrayList<ArrayList<Integer>> ans) {
        if(list.size() == num.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < num.length; i++) {
            if(!map.containsKey(num[i])) {
                while(i + 1 < num.length && num[i] == num[i + 1]) {
                    i++;
                }
                continue;
            }
            //必要的剪枝，表示只找第一个，如果前面有和该数据相等的数据，那这个位置一定是被用过了
            //假如是{1,1,2}这样的数据，剪枝只会让第一个1出现，其他的1没有机会成为第一个1，其他样例同理
            if(i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            int count = map.get(num[i]);
            if(count == 1) {
                map.remove(num[i]);
            }else {
                map.put(num[i], count - 1);
            }
            list.addLast(num[i]);
            func(num, list, map, ans);
            list.removeLast();
            map.put(num[i], count);
        }
    }

    /**
     * 存在重复数据的顺序全排列
     * 方法二：利用boolean数组单独记录每个数据是否取到
     * 时间复杂度：O(N * N!)
     * 空间复杂度：O(N)
     * @param num
     * @return
     */
    public ArrayList<ArrayList<Integer>> permuteUnique2(int[] num) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if(num.length == 0) {
            return ans;
        }
        Arrays.sort(num);
        //1.boolean类型数组记录数组的数据是否还有
        boolean[] flgs = new boolean[num.length];
        //创建临时链表，通过增删来得到各种情况，并且方便每次从最后一个位置删除
        LinkedList<Integer> list = new LinkedList<>();
        //2.遍历整个数组，仍采用插入法和回溯
        //不过这次的判断条件是哈希表里是否存在
        func(num, list, flgs, ans);
        return ans;
    }

    private void func(int[] num, LinkedList<Integer> list,
                      boolean[] flgs, ArrayList<ArrayList<Integer>> ans) {
        if(list.size() == num.length) {
            //当我们加入剪枝之后，就保证了不会有相同的一组排列，就不需要进行判断是否重复了
            ans.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < num.length; i++) {
            if(flgs[i]) {
                continue;
            }
            //必要的剪枝，表示同一位置取到的值和上次一样，没有意义
            if(i != 0 && num[i] == num[i - 1] && flgs[i - 1] == false) {
                continue;
            }
            flgs[i] = true;
            list.addLast(num[i]);
            func(num, list, flgs, ans);
            list.removeLast();
            flgs[i] = false;
        }
    }

    /**
     * 岛屿数量
     * 给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛
     * 我们只考虑上下左右为相邻。
     * 岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数
     * 深度优先遍历：dfs
     * 时间复杂度：O(N)
     * 空间复杂度：O(N),主要是递归时的深度
     * @param grid
     * @return
     */
    public int solve (char[][] grid) {
        // write code here
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {
                    //此时遇到1，一定是独立的岛屿
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    //该位置为陆地，以该位置为中心，将四周所有的陆地全部置为0
    private void dfs(char[][] grid, int i, int j) {
        grid[i][j] = '0';
        //上
        if(i - 1 >= 0 && grid[i - 1][j] == '1') {
            dfs(grid, i - 1, j);
        }
        //下
        if(i + 1 < grid.length && grid[i + 1][j] == '1') {
            dfs(grid, i + 1, j);
        }
        //左
        if(j - 1 >= 0 && grid[i][j - 1] == '1') {
            dfs(grid, i, j - 1);
        }
        //右
        if(j + 1 < grid[0].length && grid[i][j + 1] == '1') {
            dfs(grid, i, j + 1);
        }
    }

    /**
     * 岛屿数量
     * 广度优先遍历：bfs
     * 时间复杂度：O(N),最多遍历两遍
     * 空间复杂度：O(N),最大可能会存放数组一圈的坐标
     * @param grid
     * @return
     */
    public int solve2 (char[][] grid) {
        // write code here
        int count = 0;
        //广度优先遍历，需要队列
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {
                    //此时遇到1，一定是独立的岛屿
                    count++;
                    queue.offer(i);
                    queue.offer(j);
                    while(!queue.isEmpty()) {
                        int x = queue.poll();
                        int y = queue.poll();
                        grid[x][y] = '0';
                        //上
                        if(x - 1 >= 0 && grid[x - 1][y] == '1') {
                            queue.offer(x - 1);
                            queue.offer(y);
                        }
                        //下
                        if(x + 1 < grid.length && grid[x + 1][y] == '1') {
                            queue.offer(x + 1);
                            queue.offer(y);
                        }
                        //左
                        if(y - 1 >= 0 && grid[x][y - 1] == '1') {
                            queue.offer(x);
                            queue.offer(y - 1);
                        }
                        //右
                        if(y + 1 < grid[0].length && grid[x][y + 1] == '1') {
                            queue.offer(x);
                            queue.offer(y + 1);
                        }
                    }
                }
            }
        }
        return count;
    }
}
